//
// Created by EDZ on 2022/1/26.
//

#ifndef INC_2022_1_LINK_H
#define INC_2022_1_LINK_H

#include <sstream>
#include "../head/common.h"
/**
 * 给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。
 * @param pHead
 * @return
 */
ListNode* EntryNodeOfLoop(ListNode* pHead) {
    ListNode* fast = pHead;
    ListNode* slow = pHead;
    while(fast!=nullptr&&fast->next!=nullptr){
        fast = fast->next->next;
        slow = slow->next;
        if(fast==slow)
            break;
    }
    if(fast==slow&&fast->next!=nullptr){
        fast = pHead;
        while(fast!=slow){
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }else{
        return nullptr;
    }
}

/**
 * 给定一个二叉树的根节点root，该树的节点值都在数字\ 0-9 0−9 之间，每一条从根节点到叶子节点的路径都可以用一个数字表示。
 * https://www.nowcoder.com/practice/185a87cd29eb42049132aed873273e83?tpId=196&&tqId=37049&rp=1&ru=/exam/oj&qru
 * =/exam/oj&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196%26page%3D1
 * @param root
 * @return
 */
int sumNumbers(TreeNode* root) {
    if(root==NULL) return 0;
    stack<TreeNode*> s;
    stack<int> value;
    s.push(root);
    value.push(root->val);
    int total = 0;

    while(!s.empty()){
        TreeNode * node = s.top();
        s.pop();
        int v = value.top();
        value.pop();

        //叶子节点
        if(node->left==NULL&&node->right==NULL){
            total+=v;
        }else{
            if(node->right!=NULL){
                s.push(node->right);
                value.push(v*10+node->right->val);
            }
            if(node->left!=NULL){
                s.push(node->left);
                value.push(v*10+node->left->val);
            }

        }
    }
    return total;
}

/**
 * 输入一颗二叉树的根节点root和一个整数expectNumber，找出二叉树中结点值的和为expectNumber的所有路径。
 * https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=196&&tqId=37052&rp=1&ru=
 * /exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Ftab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196%26page%3D1
 * @param root
 * @param expectNumber
 * @return
 */
void init(){
    TreeNode * node = new TreeNode;
    node->val = 10;
    TreeNode * a1 = new TreeNode;
    a1->val = 5;
    TreeNode * a2 = new TreeNode;
    a2->val = 12;
    TreeNode * a3 = new TreeNode;
    a3->val = 4;
    TreeNode * a4 = new TreeNode;
    a4->val = 7;


    node->left = a1;
    node->right = a2;
    a1->left = a3;
    a1->right = a4;
}
void match(TreeNode* T,vector<vector<int>> &result,vector<int> &cur,int curVal,int expectNumber){

    if(T->left==NULL&&T->right==NULL){
        if(curVal==expectNumber)
        {
            result.push_back(cur);
            return;
        }
    }
    if(T->left!=NULL){
        vector<int> newCur(cur);
        newCur.push_back(T->left->val);
        int leftVal = T->left->val + curVal;
        match(T->left,result,newCur,leftVal,expectNumber);
    }
    if(T->right!=NULL){
        vector<int> newCur(cur);
        newCur.push_back(T->right->val);
        int rightVal = curVal + T->right->val;
        match(T->right,result,newCur,rightVal,expectNumber);
    }
}
vector<vector<int>> FindPath(TreeNode* root,int expectNumber) {
    vector<vector<int>> result;
    vector<int> a;
    if(root==NULL) return result;
    a.push_back(root->val);
    match(root,result,a,root->val,expectNumber);
    return result;
}

/**
 *给定一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.
 * @param num
 * @return
 */
TreeNode* createBFS(int l,int r,vector<int> &num){
    if(l>r) return NULL;
    int mid = (l+r)/2;
    TreeNode* root = new TreeNode(num[mid]);
    root->left = createBFS(l,mid-1,num);
    root->right = createBFS(mid+1,r,num);
    return root;
}
TreeNode* sortedArrayToBST(vector<int>& num) {
    return createBFS(0,num.size()-1,num);
}

/**
 * 求给定二叉树的最大深度，
 * @param root
 * @return
 */
int BFS(TreeNode* root,int curMax){
    if(root==NULL){
        return curMax;
    }

    return max(BFS(root->left,curMax+1),BFS(root->right,curMax+1));

}
int maxDepth(TreeNode* root) {
    return BFS(root,0);
}

/**
 * 给定一个二叉树，返回该二叉树层序遍历的结果
 * @param root
 * @return
 */
vector<vector<int> > levelOrder(TreeNode* root) {
    queue<TreeNode*> q;
    q.push(root);
    vector<vector<int>> result;
    if(root==NULL)
        return result;
    while(!q.empty()){
        int l = q.size();
        vector<int> c;
        while(l>0){
            TreeNode * node = q.front();
            c.push_back(node->val);
            q.pop();
            if(node->left) q.push(node->left);
            if(node->right) q.push(node->right);
            l--;
        }
        result.push_back(c);
    }
    return result;
}
/**
 * 如果字符串中不含有任何 'aaa'，'bbb' 或 'ccc' 这样的字符串作为子串，那么该字符串就是一个「快乐字符串」。

给你三个整数 a，b ，c，请你返回 任意一个 满足下列全部条件的字符串 s：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-happy-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param a
 * @param b
 * @param c
 * @return
 */
string longestDiverseString(int a, int b, int c) {
    string res = "";
    vector<pair<int,char>> source = {{a, 'a'},{b,'b'},{c,'c'}};
    bool flag = true;
    int i = -1;
    while(flag){
        sort(source.begin(),source.end(),[](const pair<int, char> & p1, const pair<int, char> & p2) {
            return p1.first > p2.first;
        });
        if(source[0].first>0&&(i<1||(!(res[i]==source[0].second&&res[i-1]==source[0].second)))){
            i++;
            res+=source[0].second;
            source[0].first--;
        }else if(source[1].first>0&&(i<1||(!(res[i]==source[1].second&&res[i-1]==source[1].second)))){
            i++;
            res+=source[1].second;
            source[1].first--;
        }else if(source[2].first>0&&(i<1||(!(res[i]==source[2].second&&res[i-1]==source[2].second)))){
            i++;
            res+=source[2].second;
            source[1].first--;
        }else
            break;
    }
    return res;
}

/**
 * 请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @param s
 * @return
 */
int myAtoi(string s) {
    stringstream ss(s);
    int x = 0; ss >> x;
    return x;
}
#endif //INC_2022_1_LINK_H
